Data compression systems seek to minimize an amount of information that needs to be stored or sent to convey a particular message. Data compression may be thought of as transferring a shorthand message to convey a long hand meaning. For example, if a sender and a receiver have agreed to the word “Hello” by sending the number 5, as represented by eight bits, rather than sending five seven-bit ASCII (American Standard Code for Information Interchange) characters representative of the text, “Hello,” the receiver knows that if it receives a 5, that 5 corresponds to the text “Hello.” Such a system is a data compression system because eight bits representative of the number 5 may be transferred rather than the 35 bits associated with the ACSII text for “Hello.” Various data compression schemes are known and are implemented in various systems such as, for example, data storage and data transfer.
One application in which data compression algorithms may be used is in digital communication systems. Digital communication systems typically include a mobile unit, which may be embodied in a digital cellular telephone or any other portable communication device, and an infrastructure unit, which may be embodied in a cellular base station or any other suitable communication hardware. During operation, the mobile unit and the infrastructure unit exchange digital information using one of a number of communication protocols. For example, the mobile and infrastructure units may exchange information according to a time division multiple access (TDMA) protocol, a code division multiple access (CDMA) protocol or a global system for mobile communications (GSM) protocol. The details of the TDMA protocol are disclosed in the IS-136 communication standard, which is available from the Telecommunication Industry Association (TIA). The GSM protocol is widely used in European countries and within the United States. The details of the GSM protocol are available from the European Telecommunications Standards Institute. The details of the second generation CDMA protocol are disclosed in the IS-95 communication standard. Third generation CDMA standards are typically referred to as Wideband CDMA (WCDMA). The most prevalent WCDMA standards that are currently being developed are the IS-2000 standard, which is an evolution of the IS-95 protocol, and the uniform mobile telecommunication system (UMTS) protocol, which is an evolution of the GSM protocol.
In addition to the conventional voice handling capabilities of digital communication systems, the integration of display screens into mobile units enable such units to receive graphical and text-based information. Additionally, as various other electronic devices such as, for example, personal digital assistants (PDAs) are used as wireless communication devices, such devices need to display graphical and text-based information. As mobile communication devices such as cellular telephones and PDAs receive text-based information, there is a need to compress and decompress information in an efficient manner so that mobile communication devices can provide textual information to users in a manner that is efficient from both a bandwidth perspective and a processing perspective.
One compression algorithm that is widely known and used is the Ziv and Lempel algorithm, which converts input strings of symbols or characters into fixed length codes. As strings are converted into the fixed length codes, the algorithm stores, in a dictionary, a list of strings and a list of fixed length codes to which the strings correspond. Accordingly, as the algorithm encounters strings that have already been encountered, the algorithm merely reads and transmits the fixed length code corresponding to that particular previously-encountered string. As will be readily appreciated, and as with most any compression technique, both the data transmitter and the data receiver must maintain identical codeword dictionaries containing codewords and the strings to which the codewords correspond.
Data compression for telecommunication applications is the focus of CCITT (The International Telegraph and Telephone Consultative Committee) Recommendation V.42bis, which is entitled “Data Compression Procedures for Data Circuit Terminating Equipment (DCE) Using Error Correction Procedures” and is available from the International Telecommunication Union (ITU) (1990). The Recommendation V.42bis is hereby incorporated herein by reference. While the Recommendation V.42bis provides guidelines for data compression, the Recommendation does not provide specific details regarding the implementation of a system that is compliant with V.42bis.
As will be readily appreciated by those having ordinary skill in the art, processing speed and power are of great interest to those who implement a V.42bis based compression system. To that end, U.S. Pat. No. 5,701,468 to Benayoun et al. discloses a technique for organizing a codeword dictionary having four data fields. Benayoun et al. indicates that the proffered codeword dictionary structure facilitates the easy manipulation of codewords and strings and makes accesses to memory storing the dictionary faster. Benayoun et al. discloses that an instruction state machine reads software instructions from an external memory and executes such software instructions to coordinate the operation of various portions of hardware.